package zuoshen_video;

import java.util.*;

import org.junit.Test;
public class UnionFindSetProblems {
    //最长连续子序列
    class Solution {
        public int longestConsecutive(int[] nums) {
            UnionFindSet ufs = new UnionFindSet(nums);
            int res = 0;
            for (int i = 0; i < nums.length; i++) {
                int cur = ufs.union(nums[i], nums[i] + 1);
                res = Math.max(res, cur);
            }
            ufs.showParentAndWeight();
            return res;
        }

        class UnionFindSet {
            Map<Integer, Integer> parent = new HashMap<>();
            Map<Integer, Integer> weight = new HashMap<>(); //weight是解题的关键，记录每个节点所在集合的节点个数，只有根节点的才有效
            int count;

            public UnionFindSet(int[] nums) {
                for (int i = 0; i < nums.length; i++) {
                    parent.put(nums[i], nums[i]);
                    weight.put(nums[i], 1);
                    count++;
                }
            }

            public int find(int i) {
                int p;
                if ((p = parent.get(i)) == i) return i;
                int root = find(p);
                parent.put(i, root);//路径压缩
                return root;
            }

            public int union(int num, int tar) {
                //tar是num + 1， 必须存在在parent里面【即实际存在这个数，才能进行union】
                if (!parent.containsKey(tar)) return weight.get(num);
                int root = find(num), tarRoot = find(tar);
                if (root == tarRoot) {
                    //已经合并，无需合并
                    return weight.get(root);
                }
                parent.put(tar, num);
                int sum = weight.get(root) + weight.get(tarRoot);
                weight.put(root, sum);
                count--;
                return sum;
            }

            public void showParentAndWeight() {
                System.out.println(parent);
                System.out.println(weight);
            }

            public int getWeight(int num) {
                int root = find(num);
                return weight.get(root);
            }
        }
    }

    //User合并问题
    class UserUnion{
       public class User {
            //a,b,c某一个相同，认为是同一个用户
            String a;
            String b;
            String c;
            public User(String a, String b, String c) {
                this.a = a;
                this.b = b;
                this.c = c;
            }
        }

        //设计一个通用的并查集结构
        class UnionFindSet<T> {
           Map<T, T> parent;
           Map<T, Integer> weight;
           int count;

           public UnionFindSet(Collection<T> cs) {
                parent = new HashMap<>();
                weight = new HashMap<>();
                for (T c: cs) {
                    parent.put(c, c);
                    weight.put(c, 1);
                }
                count = cs.size();
           }

           public T getParent(T t) {
               if (!parent.containsKey(t)) return null;
               return parent.get(t);
           }

           public void setParent(T t, T p) {
               if (!parent.containsKey(t)) return;
               parent.put(t, p);
           }

           public int getWeight(T t) {
            if (!weight.containsKey(t)) return -1;
            return weight.get(t);
           }

           public T find(T t) {
               T p;
               if ((p = getParent(t)) == t) return t;
               T root = find(p);
               setParent(t, root);
               return root;
           }

           public boolean isConnenct(T t1, T t2) {
               if (!parent.containsKey(t1) || !parent.containsKey(t2)) return false;
               return find(t1) == find(t2);
           }

           public void union(T t1, T t2) {
               T r1 = find(t1), r2 = find(t2);
               if (r1 == r2) return;
               int s1, s2;
               if ((s1 = weight.get(r1)) > (s2 = weight.get(r2))) {
                    weight.put(r1, s1 + s2);
                    setParent(r2, r1);
               } else {
                    weight.put(r2, s1 + s2);
                    setParent(r1, r2);
               }
               count--;
            }    
            
            //可以通过每次remove weight这个map的键值对，来通过weight.size()定义大小，可以节省一个变量
            public int getUSFSize() {
                return count;
            }
        }

        public int countUser(List<User> users) {
            Map<String, User> mapA = new HashMap<>();
            Map<String, User> mapB = new HashMap<>();
            Map<String, User> mapC = new HashMap<>();
            //此时并查集的count == size(users)
            UnionFindSet<User> usf = new UnionFindSet<>(users);
            for (User u: users) {
                if (mapA.containsKey(u.a)) mapA.put(u.a, u);
                else usf.union(mapA.get(u.a), u); //以相等的属性作为桥梁，合并两个user集合
                if (mapB.containsKey(u.b)) mapB.put(u.b, u);
                else usf.union(mapB.get(u.b), u); 
                if (mapC.containsKey(u.c)) mapC.put(u.c, u);
                else usf.union(mapC.get(u.c), u); 
            }
            return usf.count;
        }
    }

    @Test
    public void test(){
        int[] nums = new int[]{0,3,7,2,5,8,4,6,0,1};
        nums = new int[]{100,4,200,1,3,2};
        int res = new Solution().longestConsecutive(nums);
        System.out.println(res);
    }
}



/* 

        class UnionFindSet{
            int[] parent;
            int[] weight;
            int count;

            public UnionFindSet(int cap) {
                parent = new int[cap];
                weight = new int[cap];
                count = cap;
                for (int i = 0; i < cap; i++) {
                    parent[i] = i;
                    weight[i] = 1;
                }
            }

            public int find(int id) {
                if (parent[id] == id) return id;
                int root = find(parent[id]);
                parent[id] = root;
                return root;
            }

            public int union(int id1, int id2) {
                int root1 = find(id1), root2 = find(id2);
                if (root1 == root2) return count;
                else {
                    if (weight[root1] >= weight[root2]) {
                        weight[root1] += weight[root2];
                        parent[root2] = root1;
                    } else {
                        weight[root2] += weight[root1];
                        parent[root1] = root2;
                    }
                    return --count;
                }
            }
        }

*/